package ds

func FastSort(nums []int, start int, end int) {
	if start >= end {
		return
	}

	pivot := partition(nums, start, end)
	FastSort(nums, start, pivot)
	FastSort(nums, pivot+1, end)
}

func partition(nums []int, start int, end int) int {
	i := start
	j := end
	pivot := start
	for i < j {
		for i < j && nums[j] >= nums[pivot] {
			j--
		}
		for i < j && nums[i] <= nums[pivot] {
			i++
		}
		nums[i], nums[j] = nums[j], nums[i]
	}
	nums[i], nums[pivot] = nums[pivot], nums[i]
	return i
}